#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 054. 螺旋矩阵.py
@time: 2022/1/11 15:27
@desc: https://leetcode-cn.com/problems/spiral-matrix/
> 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

1. Ot(mn), Os(mn)
'''


class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix: return []
        rows, cols = len(matrix), len(matrix[0])
        # 规定几个方向、访问数组和结果列表
        visited = [[False] * cols for _ in range(rows)]
        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        total = rows * cols
        res = [0] * total

        row, col = 0, 0
        cur_direction = 0
        # 当遍历到边界或者数组被访问过了则改变访问方向
        for i in range(total):
            res[i] = matrix[row][col]
            visited[row][col] = True
            # 检查是否触碰到边界或者已经访问过了，改变方向
            next_row, next_col = row + direction[cur_direction][0], col + direction[cur_direction][1]
            if not (0 <= next_row < rows and 0 <= next_col < cols) or visited[next_row][next_col]:
                cur_direction = (cur_direction + 1) % 4
            row += direction[cur_direction][0]
            col += direction[cur_direction][1]
        return res

class Solution02(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix: return []
        m, n = len(matrix), len(matrix[0])
        total = m*n
        res = [0]*total
        # 下一步的方向
        direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        row, col = 0, 0
        # 当前遍历方向
        cd = 0
        # 访问数组
        visited = [[False]*n for _ in range(m)]
        for i in range(total):
            res[i] = matrix[row][col]
            visited[row][col] = True

            # 暂取两个变量，看下一步是否合法
            new_row, new_col = row+direction[cd][0], col+direction[cd][1]
            # 决定下一步的方向：检查是否越界或访问过了
            if not (0<=new_row<m and 0<=new_col<n) or visited[new_row][new_col]:
                # 若是的就改变方向
                cd = (cd+1)%4
            # 决定下一步的位置
            row += direction[cd][0]
            col += direction[cd][1]
        return res


if __name__ == '__main__':
    matrix = [[1,2,3],[4,5,6],[7,8,9]]
    res = Solution().spiralOrder(matrix)
    print(res)